import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

import javax.swing.tree.TreeNode;

/*
 * @lc app=leetcode.cn id=107 lang=java
 *
 * [107] 二叉树的层序遍历 II
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    /**
     * Accepted
    34/34 cases passed (1 ms)
    Your runtime beats 91.22 % of java submissions
    Your memory usage beats 88.21 % of java submissions (41.3 MB)
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root != null) {
            Deque<TreeNode> deque = new LinkedList<>();
            deque.add(root);
            trans(deque, res);
        }
        return res;
    }

    private void trans(Deque<TreeNode> deque, List<List<Integer>> res) {
        List<Integer> l = new ArrayList<>();
        Deque<TreeNode> d = new LinkedList<>();
        while (!deque.isEmpty()) {
            TreeNode t = deque.pop();
            l.add(t.val);
            if (t.left != null) {
                d.add(t.left);
            }
            if (t.right != null) {
                d.add(t.right);
            }
        }
        if (!d.isEmpty()) {
            trans(d, res);
        }
        if (!l.isEmpty()) {
            res.add(l);
        }
    }
}
// @lc code=end
